public class TextDemo {
    public static int findKthLargest(int[] nums, int k) {
        return HeapSort(nums,k-1);
    }
    private static int HeapSort(int[] array,int k){
        buildHeap(array);
        for(int i = array.length-1;i>0;i--,k--){
            swap(array,i,0);
            maxHeapify(array,0,i);
        }
        return -1;
    }
    private static void buildHeap(int[] array){
        for(int i = array.length/2-1;i>=0;i--){
            maxHeapify(array,i,array.length);
        }
    }
    private static void maxHeapify(int[] array,int i,int heapSize){
        int left = 2*i+1;
        int right = left+1;
        int last = i;
        if(left<heapSize && array[left]>array[last]){
            last = left;
        }
        if(right<heapSize && array[right]>array[last]){
            last = right;
        }
        if(last!=i){
            swap(array,last,i);
            maxHeapify(array,last,heapSize);
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{3,2,1,5,6,4};
        findKthLargest(array,2);
    }

    public static void mergeSort(int[] array){
        if(array.length==0) return ;
        int[] result = new int[array.length];
        mergeSort(array,0,array.length-1,result);
    }
    private static void mergeSort(int[] array,int start,int end,int[] result){
        if(start==end) return ;
        int middle = (start+end)/2;
        mergeSort(array,start,middle,result);
        mergeSort(array,middle+1,end,result);
        merge(array,start,end,result);
    }
    private static void  merge(int[] array,int start,int end,int[] result){
        int end1 = (start+end)/2;
        int start2 = end1+1;
        int index1 = start;
        int index2 = start2;
        while(index1<=end1 && index2<=end){
            if(array[index1]<=array[index2]){
                result[index1+index2-start2] = array[index1++];
            }else{
                result[index1+index2-start2] = array[index2++];
            }
        }
        while(index1<=end1){
            result[index1+index2-start2] = array[index1++];
        }
        while(index2<=end){
            result[index1+index2-start2] = array[index2++];
        }

    }
    public static void mergeSort1(int[] array){
        if(array.length==0) return ;
        int[] result = mergeSort1(array,0,array.length-1);
        for(int i = 0;i<result.length;i++){
            array[i] = result[i];
        }
    }

    private static int[] mergeSort1(int[] array,int start,int end){
        if(start==end) return new int[]{array[start]};
        int middle = (start+end)/2;
        int[] left = mergeSort1(array,start,middle);
        int[] right = mergeSort1(array,middle+1,end);
        return merge1(left,right);
    }
    public static int[] merge1(int[] array1,int[] array2){
        int[] result = new int[array1.length+ array2.length];
        int index1 = 0;
        int index2 = 0;
        while(index1<array1.length && index2<array2.length){
            if(array1[index1]<=array2[index2]){
                result[index1+index2] = array1[index1++];
            }else{
                result[index1+index2] = array2[index2++];
            }
        }
        while(index1< array1.length){
            result[index1+index2] = array1[index1++];
        }
        while(index2<array2.length){
            result[index1+index2] = array2[index2++];
        }
        return result;
    }
    public static void quickSort(int[] array){
        quickSort(array,0,array.length-1);
    }
   public static void quickSort(int[] array,int left,int right){
        if(left>=right){
            return ;
        }
        int pivot = partition(array,left,right);
        quickSort(array,left,pivot-1);
        quickSort(array,pivot+1,right);
   }
   private static int partition(int[] array,int start,int end){
        int pivot = array[start];
        int left = start+1;
        int right = end;
        while(left<right){
            while(left<right && array[left]<=pivot){
                left++;
            }
            while(left<right && array[right]>=pivot){
                right--;
            }
            if(left<right){
                swap(array,left,right);
                left++;
                right--;
            }
        }
        if(left==right && array[right]>pivot) right--;
        swap(array,start,right);
        return right;
   }
   private static int partition1(int[] array,int start,int end){
        int left = start+1;
        int right = end;
        int pivot = array[start];
        while(left<right){
            while(left<right && array[left]<=pivot){
                left++;
            }
            if(left!=right){
                swap(array,left,right);
                right--;
            }
        }
        //如果left和right相等，单独比较array[right]和pivot
        if(left==right && array[right]>pivot){
            right--;
        }
        //
        if(right!=start){
            swap(array,start,right);
        }
        return right;
   }
    private static void swap(int[] array,int x,int y){
        int tem = array[x];
        array[x] = array[y];
        array[y] = tem;
    }

}
